The Golden Ticket by Fortnow Lance

Author:Fortnow, Lance [Fortnow, Lance]
Language: eng
Format: epub
Publisher: Princeton University Press
Published: 2013-03-26T21:00:00+00:00

The Gödel Letter

In 1956 Kurt Gödel wrote a letter to John von Neumann, one of the pioneers of computer science and many other fields. In this letter (written in German), Gödel talks about the satisfiability problem and formulates the P versus NP question in different terminology. He suggests that if we lived in a world where P = NP, “the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. … Now it seems to me, however, to be completely within the realm of possibility.” This letter predates the papers of Cook and Levin by fifteen years.

We do not know if von Neumann responded or even saw this letter. Von Neumann had cancer at the time of the letter and passed away in 1957. The letter itself was unknown to the general scientific community until the late 1980s, well after the P versus NP problem was firmly established as a major open question. Gödel passed away in 1978 but was not in the right mental state in those last years of his life to notice that Cook had restated his question.

Since Gödel discovered the P versus NP problem years before Cook and Levin, why don’t we call whether P = NP “Gödel’s problem,” and give him the credit? Science, for better or for worse, uses the Columbus principle: Christopher Columbus is famous not for being the first person to discover America but for being the last person to discover America. Gödel himself was not blameless. He didn’t realize the importance of the question he raised with von Neumann and never mentioned it in a public venue. Cook and Levin still have the first published papers that state the P versus NP problem.

In honor of Gödel’s fundamental work in logic and the Gödel letter, the theoretical computer science community initiated the Gödel Prize in 1993 to recognize recent outstanding research papers in the field.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.